#include <bits/stdc++.h>

using namespace std;

// 重复叠加字符串匹配
// 给定两个字符串a和b，寻找重复叠加字符串a的最小次数，使得字符串b成为叠加后的字符串a的子串
// 如果不存在则返回-1
// 字符串"abc"重复叠加0次是""
// 重复叠加1次是"abc"
// 重复叠加2次是"abcabc"
// 测试链接 : https://leetcode.cn/problems/repeated-string-match/

class Solution 
{
public:
    using ull = unsigned long long;
    static const int MAXN = 30001;
    char s[MAXN];
    int base = 499;
    ull p[MAXN], h[MAXN];

    void build(int n)
    {
        p[0] = 1;
        for(int i = 1; i < n; ++i)
        {
            p[i] = p[i - 1] * base;
        }
        h[0] = s[0] - 'a' + 1;
        for(int i = 1; i < n; ++i)
        {
            h[i] = h[i - 1] * base + s[i] - 'a' + 1;
        }
    }

    ull hash(int l, int r)
    {
        ull ans = h[r];
        ans -= l == 0 ? 0 : (h[l - 1] * p[r - l + 1]);
        return ans;
    }

    int repeatedStringMatch(string s1, string s2) 
    {
        int n = s1.size(), m = s2.size();
        // m / n 向上取整
        int k = (m + n - 1) / n;
        int len = 0;
        for(int cnt = 0; cnt <= k; ++cnt)
        {
            for(int i = 0; i < n; ++i)
            {
                s[len++] = s1[i];
            }
        }
        build(len);
        ull h2 = s2[0] - 'a' + 1;
        for(int i = 1; i < m; ++i) h2 = h2 * base + s2[i] - 'a' + 1;
        for(int l = 0, r = m - 1; r < len; ++l, ++r)
        {
            if(hash(l, r) == h2)
            {
                return r < n * k ? k : (k + 1);
            }
        }
        return -1;
    }
};